package niuke.week4;

import java.util.HashMap;
import java.util.Scanner;

public class LRU02 {
    Node head;//最早访问
    Node tail;//最晚访问
    int cap;//容量
    HashMap<Integer,Node>map;

    public LRU02(int cap) {
        this.cap = cap;
        this.map = new<Integer,Node>HashMap();
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int op = sc.nextInt();
        int cap = sc.nextInt();

        LRU02 lru = new LRU02(cap);
        for (int i = 0; i < op; i++) {
            int opt = sc.nextInt();
            if(opt==1){
                lru.set(sc.nextInt(),sc.nextInt());
            }else{
                int res = lru.get(sc.nextInt());
                System.out.println(res);
            }
//            lru.print();
        }
    }


    public  int  get(int k){
        Node node = map.get(k);
        if(node==null)
            return  -1;
        blance(node);
        return  node.value;

    }

    public  void  print(){
           Node curNode =head;
            while (curNode!=null) {
                System.out.print(curNode.key + "-->");
                curNode = curNode.next;
            }
            System.out.println();
    }

    public  void set(int k,int v){
        Node node = new Node(k, v);
        map.put(k,node);
        if(map.size()==1){//第一个节点
            tail = node;
            head = node;
            return;
        }
        blance(node);
        if(map.size()>cap)
            remove();
    }

    public  void remove(){
        Node headNext = head.next;
        head.next = null;
        map.remove(head.key);

        head = headNext;
    }

    public void  blance(Node node){
        if(node==tail)//B C node
            return;

        if(node==head){//node B C
            node.next.pre =null;
            head = node.next;

            node.next = null;
        }
        //  B C node D E
        if(node.pre!=null)
            node.pre.next = node.next;
        if(node.next!=null)
             node.next.pre = node.pre;

        //A node B C ---> A B C node
        node.pre = tail;
        tail.next = node;
        node.next=null;
        tail = node;
    }
}

class Node{
    Node next;
    Node pre;
    int value;
    int key;

    public Node(int key,int  value) {
        this.value = value;
        this.key = key;
    }

    public Node() {
    }
}